class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def isPalindrome(head):
    if not head or not head.next:
        return True

    # 1. 快慢指针找到中点
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # 2. 反转后半部分链表
    prev = None
    curr = slow
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    # 3. 比较前半部分和反转后的后半部分
    first, second = head, prev
    while second:
        if first.val != second.val:
            return False
        first = first.next
        second = second.next

    return True

# # 方法二：
# def isPalindrome(head):
#     curr = head
#     num = []
#     while curr:
#         num.append(curr.val)
#         curr = curr.next
#     return num == num[::-1]

# 辅助函数：列表转链表
def list_to_linkedlist(arr):
    dummy = ListNode(0)
    curr = dummy
    for val in arr:
        curr.next = ListNode(val)
        curr = curr.next
    return dummy.next

# 辅助函数：打印链表
def print_linkedlist(head):
    res = []
    while head:
        res.append(str(head.val))
        head = head.next
    print(" -> ".join(res))

if __name__ == '__main__':
    # 测试用例
    arr1 = [1, 2, 2, 1]
    head1 = list_to_linkedlist(arr1)
    print(isPalindrome(head1))
